//
// Created by yangchao on 2022/5/9.
// 53. 最大子数组和: https://leetcode.cn/problems/maximum-subarray/
//

#include <vector>
using namespace std;

class MaxSubArray{
public:
    int maxSubArray(vector<int>& nums) {
        int dp[nums.size()];
        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = nums[i];
            if (dp[i-1] > 0) {
                dp[i] += dp[i-1];
            }
            res = max(res,dp[i]);
        }
        return res;
    }
};
